import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Random;

/**Cette classe correspond à la description d"une fourmi dans le cas de notre algorithme, ainsi
 * que les fonctions et les méthodes que nous pourrons lui appliquer pour faire avancer la
 * recherche de plus court chemin.
 * @author Pocman
 *
 */

public class Ant implements Runnable {
	private int Id;
	private Thread thread;
	private AntSolution s;
	private int noeudActuel;
	private ArrayList<Integer> nav;
	private int compteur;
	private AntListeCandidat listeCandidat;
	private static AntColony antColony;
	private static int compteurID = 0;
	public static AntInstance antInstance;
	private static int nbSommet;

	
	public static AntSolution meilleurChemin = null;
	public static AntSolution meilleurCheminIteration = null;

	private static final double BETA = (double) 2;// pondération rapport entre
													// pheromones et inverse
													// distance
	private static final double GAMMA = (double) 0.75; /* initiative */
	private static final double DISPERSION = (double) 0.1; // coefficient de
															// dispersion

	private static final Random R = new Random(System.currentTimeMillis());
	/**constructeur d'une fourmi
	 * @throws Exception
	 */
	public Ant() throws Exception {
		Ant.compteurID++;
		this.Id = Ant.compteurID;
		this.listeCandidat=new AntListeCandidat();
		this.nav = new ArrayList<Integer>();
	}

	public static void setAntInstance(AntInstance antInstance) {
		Ant.antInstance = antInstance;
		nbSommet = Ant.antInstance.getInstance().getNbSommets();
	}
	
	/**fonction qui retourne la solution du meilleur chemin de la fourmi
	 * @return
	 */
	public static Solution getMeilleurChemin() {
		return Ant.meilleurChemin.getSolution();
	}
	
	/**fonction qui initialise l'algorithme
	 * @throws Exception
	 */
	public void init() throws Exception {

		this.noeudActuel = (int) ((Ant.antInstance.getInstance().getNbSommets()) * R
				.nextDouble());
		
		this.listeCandidat.init();


		this.s = new AntSolution(Ant.antInstance.getInstance());
		
		this.compteur = 0;
		
		this.nav.clear();

		this.s.setNoeud(this.noeudActuel, this.compteur);
		this.compteur++;

		this.listeCandidat.retirer(this.noeudActuel);

		Ant.meilleurCheminIteration = null;
	}
	
	/**méthode qui permet le démarrage de recherche de meilleur chemin
	 * @throws Exception
	 */
	public void start() throws Exception {
		init();
		this.thread = new Thread(this);
		thread.setName("Ant " + Id);
		thread.start();
	}

	public Thread getThread() {
		return this.thread;
	}
	
	/**méthode qui permet à une fourmi de passer de noeud en noeud
	 */
	public void run() {
		int nextNode = -1;

		while (!this.listeCandidat.isEmpty()) {
			synchronized (Ant.antInstance) {
				try {
					nextNode = getNextNode();
				} catch (Exception e1) {

					e1.printStackTrace();
				}
				try {
					this.s.setNoeud(nextNode, this.compteur);
					this.compteur++;
				} catch (Exception e) {

					e.printStackTrace();
				}

				this.noeudActuel = nextNode;
				this.listeCandidat.retirer(this.noeudActuel);
			}
		}

		try {
				antColony.deuxOpt(this.s);
			if (Ant.meilleurCheminIteration != null && this.s.isBest(Ant.meilleurCheminIteration)) {
				Ant.meilleurCheminIteration = this.s;
			}
			else if(Ant.meilleurCheminIteration == null){
				Ant.meilleurCheminIteration = this.s;				
			}
		} catch (Exception e) {
			e.printStackTrace();
		}

	}
	
	/**fonction qui retourne la valeur du noeud suivant
	 * @return
	 * @throws Exception
	 */
	private int getNextNode() throws Exception {
		int nextNode = -1;
		int noeud = -1;
		this.nav = this.listeCandidat.getNoeudAVisiter(this.noeudActuel);
		
		if (R.nextDouble() < Ant.GAMMA) { // exploitation

			double valeurPheromones = -1;
			double valeurMaximalePheromones = -1;
			Iterator<Integer> it = this.nav.iterator();
					
			while (it.hasNext()) {
				
				noeud = it.next();

				valeurPheromones = Ant.antInstance.getTau(this.noeudActuel,
						noeud )
						* Math.pow(
								1 / Ant.antInstance.getDistance(this.noeudActuel , noeud ),
								Ant.BETA);
				if (valeurMaximalePheromones < valeurPheromones) {
					nextNode = noeud;
					valeurMaximalePheromones = valeurPheromones;
				}

			}
		} else { // exploration

			double sum = 0;
			Iterator<Integer> it = this.nav.iterator();
			HashMap<Integer, Double> valeursPheromones = new HashMap<Integer, Double>();

			while (it.hasNext()) {
				noeud = it.next();
				valeursPheromones.put(
						noeud,
						Ant.antInstance.getTau(this.noeudActuel, noeud)
								* Math.pow(1 / this.antInstance.getDistance(this.noeudActuel, noeud), Ant.BETA));
			}
			sum = sommeHashMap(valeursPheromones);

			it = this.nav.iterator();
			double p = R.nextDouble() * sum;

			double sumPheromones = 0;
			while (p >= sumPheromones && it.hasNext()) {
				noeud = it.next();
				sumPheromones += valeursPheromones.get(noeud);
				if (p <= sumPheromones) {
					nextNode = noeud;
				}
			}

		}

		return nextNode;
	}
	
	/**méthode qui permet la mise à jour de la tournée d'une fourmi
	 * @param utiliserCheminIt
	 * @throws Exception
	 */
	public static void miseAJourFinTournee(boolean utiliserCheminIt)
			throws Exception {

		for (int i = 0; i < Ant.nbSommet; i++) {
			for (int j = 0; j < Ant.nbSommet; j++) {
				if (i != j) {
				
					Ant.antInstance.miseAJourTau(i, j, (1 - Ant.DISPERSION)
							* Ant.antInstance.getTau(i, j));
					
					if (utiliserCheminIt){
						if(Ant.meilleurCheminIteration.isArc(i, j)) {
						Ant.antInstance.miseAJourTau(i, j,
								Ant.antInstance.getTau(i, j) +  1
										/ Ant.meilleurCheminIteration.getLongueurSolution());
						}
					}
					else if (Ant.meilleurChemin.isArc(i, j)) {
						Ant.antInstance.miseAJourTau(i, j,
								Ant.antInstance.getTau(i, j) +  1
										/ Ant.meilleurChemin.getLongueurSolution());
					}
					}
				
				
				

			}
		}
	}

	public double sommeHashMap(HashMap<Integer, Double> map) {
		Iterator<Integer> it = map.keySet().iterator();
		double sum = 0;
		while (it.hasNext()) {
			sum += map.get(it.next());
		}
		return sum;
	}
	
	/**fonction qui retourne true si le chemin est meilleur, false sinon
	 * @return
	 */
	public static boolean miseAJourMeilleurChemin() {
		if(Ant.meilleurChemin == null){
			Ant.meilleurChemin = Ant.meilleurCheminIteration;
			return true;
		}
		else if (Ant.meilleurCheminIteration.isBest(Ant.meilleurChemin)) {
			Ant.meilleurChemin = Ant.meilleurCheminIteration;
			return true;
			
		}
		else
			return false;
	}
	
	public static void setAntColony(AntColony a){
		Ant.antColony = a;
	}

}